【LeetCode 70】Climbing Stairs 爬楼梯

发表于 | 分类于

[LeetCode 70]Climbing Stairs 爬楼梯

Problem description:

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example:

1
2
3
4
5
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

问题描述:

假设你正在爬楼梯。需要 n 步你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

说明：给定 n 是一个正整数。

示例:

1
2
3
4
5
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 步 + 1 步
2.  2 步

Solution:

通过归纳可知符合斐波那契数列。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int climbStairs(int n) {
        if(n==1)
            return 1;
        if(n==2)
            return 2;
        int f1=1;
        int f2=2;
        int sum=0;
        for(int i=2;i<n;i++){

            sum=f1+f2;
            f1=f2;
            f2=sum;

        }
        return sum;
    }
}
Thanks!